We represent graphs using vertices (V) and edges (E), and access them efficiently with an adjacency list.
- A graph consists of a set of vertices (or nodes) and a set of edges connecting pairs of vertices.
- Edges can be undirected (a simple line, like a two-way street) or directed (an arrow, like a one-way street).
- For coding, a common and efficient representation for sparse graphs is an adjacency list.
- An adjacency list is essentially a dictionary where each key is a vertex, and its value is a list of that vertex's neighbors.
- This structure allows for fast neighbor access (in O(degree(u)) time) and enables overall graph traversals in O(V+E) time.
Core Concepts & Notation
| Concept | Notation | Example |
|---|---|---|
| Vertex Set | V | {A, B, C, D} |
| Edge Set | E | {(A,B), (B,C), ...} |
| Adjacency List | G[u] | G['A'] = ['B', 'D'] |